package sliding_window

import "sort"

func fourSum2(nums []int, target int) [][]int {
	sort.Ints(nums)
	var res [][]int
	for i := 0; i < len(nums)-3; i++ {
		if i != 0 && nums[i] == nums[i-1] {
			continue
		}
		subThreeSum(&res, nums[i], nums[i+1:], target-nums[i])
	}
	return res
}
func subThreeSum(res *[][]int, first int, nums []int, target int) {
	nlen := len(nums)
	for i := 0; i < nlen-2; i++ {
		if i != 0 && nums[i] == nums[i-1] {
			continue
		}

		left, right := i+1, nlen-1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum == target {
				*res = append(*res, []int{first, nums[i], nums[left], nums[right]})
				//去重
				for left < right && nums[left] == nums[left+1] {
					left++
				}
				for left < right && nums[right] == nums[right-1] {
					right--
				}
				left++
				right--
			} else if sum < target {
				//去重
				for left < right && nums[left] == nums[left+1] {
					left++
				}
				left++
			} else {
				for left < right && nums[right] == nums[right-1] {
					right--
				}
				right--
			}
		}
	}
}

func fourSum1(nums []int, target int) [][]int {
	//排序
	sort.Ints(nums)
	var results [][]int
	for i := 0; i < len(nums); i++ {
		for i1 := i + 1; i1 < len(nums); i1++ {
			sum := -nums[i1] - nums[i] + target
			front := i1 + 1
			back := len(nums) - 1
			for front < back {
				temp := nums[front] + nums[back]
				if temp < sum {
					front++
				} else if temp > sum {
					back--
				} else {
					reSub := make([]int, 4)
					reSub[0] = nums[i1]
					reSub[1] = nums[front]
					reSub[2] = nums[back]
					reSub[3] = nums[i]
					results = append(results, reSub)

					for front < back && nums[front] == reSub[1] {
						front++
					}

					for front < back && nums[back] == reSub[2] {
						back--
					}
				}
			}
			for i1+1 < len(nums) && nums[i1+1] == nums[i1] {
				i1++
			}
		}

		for i+1 < len(nums) && nums[i+1] == nums[i] {
			i++
		}
	}
	return results
}

func fourSum(nums []int, target int) (results [][]int) {
	//排序
	sort.Ints(nums)
	n := len(nums)

	for i := 0; i < n-3 && nums[i]+nums[i+1]+nums[i+2]+nums[i+3] <= target; i++ {
		if i > 0 && nums[i] == nums[i-1] || nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target {
			continue
		}
		for j := i + 1; j < n-2 && nums[i]+nums[j]+nums[j+1]+nums[j+2] <= target; j++ {
			if j > i+1 && nums[j] == nums[j-1] || nums[i]+nums[j]+nums[n-2]+nums[n-1] < target {
				continue
			}
			for left, right := j+1, n-1; left < right; {
				if sum := nums[i] + nums[j] + nums[left] + nums[right]; sum == target {
					results = append(results, []int{nums[i], nums[j], nums[left], nums[right]})
					for left++; left < right && nums[left] == nums[left-1]; left++ {
					}
					for right--; left < right && nums[right] == nums[right+1]; right-- {

					}
				} else if sum < target {
					left++
				} else {
					right--
				}
			}
		}
	}
	return
}
